package com.hy.backtracking3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FullPermutation2 {


    /**
     * 47.全排列 II
     * 力扣题目链接
     *
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     *
     * 示例 1：
     *
     * 输入：nums = [1,1,2]
     * 输出： [[1,1,2], [1,2,1], [2,1,1]]
     * 示例 2：
     *
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     *
     * 思路
     * 如果对回溯算法基础还不了解的话，我还特意录制了一期视频：带你学透回溯算法（理论篇） 可以结合题解和视频一起看，希望对大家理解回溯算法有所帮助。
     *
     * 这道题目和46.全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。
     *
     * 这里又涉及到去重了。
     *
     * 在40.组合总和II 、90.子集II我们分别详细讲解了组合问题和子集问题如何去重。
     *
     * 那么排列问题其实也是一样的套路。
     *
     * 还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
     *
     * 我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：
     */

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> getFullPermutation2(int [] num){
        boolean[] used = new boolean[num.length];
        // 填充属性
        Arrays.fill(used, false);
        fullPermutation2(num,used);
        return res;
    }
    public void fullPermutation2(int [] num,boolean [] used){
        // 回溯 终止条件
        if (path.size() == num.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            //这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。
            //对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i> 0 && num[i] == num[i-1] && used[i-1] == true){
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if(used[i] == false){
                //标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                used[i] = true;
                path.add(num[i]);
                //回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                fullPermutation2(num,used);
                path.remove(path.size() -1);
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        FullPermutation2 fullPermutation2 = new FullPermutation2();
        int [] num = {1,2,2};
        System.out.println("res: "+fullPermutation2.getFullPermutation2(num));
    }
}
